1. Technical Field
The present invention generally relates to decoding encoded data, and in particular to decoding encoded data that is encoded by replacing each of multiple symbols with a bit string.
2. Description of the Related Art
Deflate compression (RFC1951) is a compression method used as a basis for ZLIB (RFC1950) and GZIP (RFC1952), which are data compression formats currently widely used in computers. In this method, data is compressed by using a coding technique called Huffman coding. In Huffman coding, each single-byte character repeatedly appearing in data is assigned a variable-length code in accordance with the frequency of appearance. The coding can be performed more efficiently if a frequently appearing character is assigned a code having a short bit length while a less-frequently appearing character is assigned a code having a long bit length.
For efficient Huffman coding, a Huffman table, which stores a code assigned to each character, is created and added to compressed data. Then, the compressed data is decoded by reference to the Huffman table.
However, adding a large-size Huffman table to the compressed data lowers the compression rate. To improve this compression rate, the Huffman table itself is also compressed in deflate compression (RFC1951).
Specifically, in deflate compression, a Huffman table stores the length of a code (bit length) assigned to each character, instead of storing a code assigned to each character. It is defined, in deflate compression, that codes in a group having the same bit length are assigned respectively to characters in the ASCII code order (in the alphabetical order if target characters are alphabets). In this way, a code for each character can be uniquely determined based on the bit length.
Conventionally, some techniques have been proposed as techniques for decoding encoded data by using a Huffman table (see Japanese Patent Application Publication No. Hei 7-170197 and Japanese Patent Application Publication No. Hei 8-167855, for example).
In Japanese Patent Application Publication No. Hei 7-170197, the number of code bits to be fetched first for decoding is written to a decode table. Then, with the “root” of a code tree set as a target node, it is judged whether a “child” of the target node is a “leaf (terminal node)” or an intermediate node. If the child is a “leaf,” a decode termination instruction for returning an event value corresponding to the leaf is written to the decode table. If the child is an intermediate node, on the other hand, a decode continuation instruction for returning an address to be accessed next and the number of code bits to be extracted next for the decoding is written to the decode table. Thereafter the above operations are repeated recursively by setting the “child” as a new target node.
In Japanese Patent Application Publication No. Hei 8-167855, in a Huffman decoding circuit, an encoded-data fetching unit fetches a code bit string supplied externally and then creates encoded data having a certain bit length, and a Huffman-decoding look-up table outputs, upon receipt of the encoded data created by the encoded-data fetching unit, decoded data corresponding to a code of high-order bits of the encoded data and the bit length of the code. The encoded-data fetching unit discards high-order data of an amount corresponding to the bits of the bit length outputted by the Huffman-decoding look-up table, fetches new data supplied externally in return, and thereby creates encoded data having the certain bit length.
To decode compressed data by using a compressed Huffman table in any of the above-described methods, the following steps need to be taken: (1) extracting a bit length; and (2) decoding a code based on the extracted bit length. In this process, to perform the step (2) at a high speed, the Huffman table needs to be subjected to bitwise sorting in advance.
However, the sorting processing is required to be performed repeatedly the same number of times as the number of the codes. For this reason, if the number of the codes is large, a long time is required for the processing.